#define  _CRT_SECURE_NO_WARNINGS

#include<iostream>

using namespace std;

void _MergeSort(int* arr, int left, int right, int* temp)
{
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) / 2;
    _MergeSort(arr, left, mid, temp);
    _MergeSort(arr, mid + 1, right, temp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            temp[index++] = arr[begin1++];
        }
        else
        {
            temp[index++] = arr[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        temp[index++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        temp[index++] = arr[begin2++];
    }
    for (int i = left; i <= right; i++)
    {
        arr[i] = temp[i];
    }
}

void MergeSort(int* arr, int n)
{
    int* temp = (int*)malloc(sizeof(int) * n);
    _MergeSort(arr, 0, n - 1, temp);
    free(temp);
    temp = NULL;
}

void sortColors(int* nums, int numsSize)
{
    MergeSort(nums, numsSize);
}
